package com.leetcode.partition11;

import java.io.*;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @author `RKC`
 * @date 2022/1/11 15:13
 */
@SuppressWarnings("all")
public class LC1036逃离大迷宫 {

    private static final int P = 131, N = (int) 1e6;
    private static final int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static int limited = (int) 1e5;
    private static Set<Integer> blockedSet = new HashSet<>();

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        int x1 = Integer.parseInt(s[0]), y1 = Integer.parseInt(s[1]);
        s = reader.readLine().split("\\s+");
        int x2 = Integer.parseInt(s[0]), y2 = Integer.parseInt(s[1]);
        int k = Integer.parseInt(reader.readLine());
        int[][] blocked = new int[k][2];
        for (int i = 0; i < k; i++) {
            s = reader.readLine().split("\\s+");
            int x3 = Integer.parseInt(s[0]), y3 = Integer.parseInt(s[1]);
            blocked[i][0] = x3;
            blocked[i][1] = y3;
        }
        writer.write(isEscapePossible(blocked, new int[]{x1, y1}, new int[]{x2, y2}) + "\n");
        writer.flush();
    }

    public static boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        //将有障碍的地方都存到set中便于查找，因为行列都很大，所以使用一个质数来进行转换
        for (int[] pair : blocked) blockedSet.add(hash(pair));
        //设障碍物有n个，那么n个障碍物围成的最大面积是 n(n-1)/2，如果bfs过程中超出了这个值，就说明必定围不住
        int n = blocked.length;
        limited = n * (n - 1) / 2;
        return bfs(source, target) && bfs(target, source);
    }

    private static boolean bfs(int[] source, int[] target) {
        Set<Integer> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        queue.add(source);
        visited.add(hash(source));
        while (!queue.isEmpty() && visited.size() <= limited) {
            int[] pair = queue.poll();
            if (pair[0] == target[0] && pair[1] == target[1]) return true;
            for (int[] dir : dirs) {
                int x = pair[0] + dir[0], y = pair[1] + dir[1];
                if (x < 0 || x >= N || y < 0 || y >= N) continue;
                int[] next = {x, y};
                //如果扩展的节点是障碍或者已经被扩展过，就不再入队进行扩展
                int hash = hash(next);
                if (blockedSet.contains(hash) || visited.contains(hash)) continue;
                queue.add(next);
                visited.add(hash);
            }
        }
        //超过了所能围成的最大面积就能突围
        return visited.size() > limited;
    }

    private static int hash(int[] pair) {
        return pair[0] * P + pair[1];
    }
}
